import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-22
 * Time: 9:14
 */
public class Day4 {
    //121.买卖股票的最佳时机 - 标记
    public int maxProfit(int[] prices) {
        if (prices.length <= 1){
            return 0;
        }
        int min = prices[0];
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            max = Math.max(max, prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return max;
    }

    //136.只出现一次的数字
    public int singleNumber(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            nums[0] ^= nums[i];
        }
        return nums[0];
    }

    //169.多数元素  - 标记
    public int majorityElement(int[] nums) {
        int ret = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (ret == nums[i]){
                count++;
            }else{
                count--;
            }
            if (count == 0){
                ret = nums[i];
                count = 1;
            }
        }
        return ret;
    }

    //387.字符串中的第一个唯一字符 - 标记
    public int firstUniqChar1(String s) {
        int[] array = new int[27];
        char[] ret = s.toCharArray();
        for (int i = 0; i < ret.length; i++) {
            array[ret[i] - 97]++;
        }
        for (int i = 0; i < ret.length; i++) {
            if (array[ret[i] - 97] == 1){
                return i;
            }
        }
        return -1;
    }
    public int firstUniqChar2(String s) {
        Map<Character, Integer> map;
        map = new HashMap<>(26);
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }
        return -1;
    }

    //1700.无法吃午餐的学生数量 - 标记
    public int countStudents1(int[] students, int[] sandwiches) {
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < students.length; i++) {
            queue.offer(students[i]);
        }
        for (int i = sandwiches.length - 1; i >= 0; i--) {
            stack.push(sandwiches[i]);
        }

        int count = 0;
        while (queue.size() != 0){
            if (queue.peek() == stack.peek()){
                queue.poll();
                stack.pop();
                count = 0;
            }else{
                int num = queue.poll();
                queue.offer(num);
                count++;
            }
            if (count == queue.size()){
                break;
            }
        }
        return count;
    }

    public int countStudents(int[] students, int[] sandwiches) {
        int[] cnt = new int[2];
        for(int student : students) cnt[student]++;
        for(int sandwich : sandwiches){
            if (cnt[sandwich] > 0){
                cnt[sandwich]--;
            }else{
                break;
            }
        }
        return cnt[0] + cnt[1];
    }
}
//933.最近的请求次数 - 标记
class RecentCounter1 {

    Queue<Integer> queue;
    public RecentCounter1(){
        queue = new LinkedList<>();
    }

    public int ping(int t) {
        queue.offer(t);
        while(true){
            int ret = queue.peek();
            if (ret >= t - 3000 && ret <= t){
                break;
            }
            queue.poll();
        }

        return queue.size();
    }
}
class RecentCounter {

    int[] ret;
    int left, right;

    public RecentCounter() {
        ret = new int[10001];
        left = 0;
        right = 0;
    }

    public int ping(int t) {
        ret[right++] = t;
        while (left < right && ret[left] < t - 3000){
            left++;
        }
        return right - left;
    }
}

